|
|
Intersection representations of graphs
Töpfer, Martin ; Jelínek, Vít (advisor) ; Pangrác, Ondřej (referee)
This thesis is devoted to the outer and grounded string representations of graphs and their subclasses. A string representation of a graph is a set of strings (bounded continuous curves in a plane), where each string corresponds to one vertex of the graph. Two strings intersect each other if and only if the two corresponding vertices are adjacent in the original graph. An outer string graph is a graph with a string representation where strings are realized inside a disk and one endpoint of each string lies on the boundary of the disk. Similarly, in case of grounded string graphs the strings lie in a common half- plane with one endpoint of each string on the boundary of the half-plane. We give a summary of subclasses of grounded string graphs and proves several results about their mutual inclusions and separations. To prove those, we use an order-forcing lemma which can be used to force a particular order of the endpoints of the string on the boundary circle or boundary line. The second part of the thesis contains proof that recognition of outer string graphs is NP-hard. 1
|
|
|
On the Hardness of General Caching
Folwarczný, Lukáš ; Sgall, Jiří (advisor) ; Koutecký, Martin (referee)
Caching (also known as paging) is a classical problem concerning page re- placement policies in two-level memory systems. General caching is its vari- ant with pages of different sizes and fault costs. We aim at a better charac- terization of the computational complexity of general caching in the offline version. General caching in the offline version was recently shown to be strongly NP- hard, but the proof needed instances of caching with pages larger than half of the cache size. The primary result of this work addresses this problem as we prove: General caching is strongly NP-hard even when page sizes are limited to {1, 2, 3}. In the structural part of this work, a new simpler proof for the full characterization of work functions by layers for classical caching is given and then extended to caching with variable cache size. We invent two algorithms for restricted instances of general caching building on results around caching with variable cache size.
|
|
|
Intersection representations of graphs
Töpfer, Martin ; Jelínek, Vít (advisor) ; Pangrác, Ondřej (referee)
This thesis is devoted to the outer and grounded string representations of graphs and their subclasses. A string representation of a graph is a set of strings (bounded continuous curves in a plane), where each string corresponds to one vertex of the graph. Two strings intersect each other if and only if the two corresponding vertices are adjacent in the original graph. An outer string graph is a graph with a string representation where strings are realized inside a disk and one endpoint of each string lies on the boundary of the disk. Similarly, in case of grounded string graphs the strings lie in a common half- plane with one endpoint of each string on the boundary of the half-plane. We give a summary of subclasses of grounded string graphs and proves several results about their mutual inclusions and separations. To prove those, we use an order-forcing lemma which can be used to force a particular order of the endpoints of the string on the boundary circle or boundary line. The second part of the thesis contains proof that recognition of outer string graphs is NP-hard. 1
|
|
|
On the Hardness of General Caching
Folwarczný, Lukáš ; Sgall, Jiří (advisor) ; Koutecký, Martin (referee)
Caching (also known as paging) is a classical problem concerning page re- placement policies in two-level memory systems. General caching is its vari- ant with pages of different sizes and fault costs. We aim at a better charac- terization of the computational complexity of general caching in the offline version. General caching in the offline version was recently shown to be strongly NP- hard, but the proof needed instances of caching with pages larger than half of the cache size. The primary result of this work addresses this problem as we prove: General caching is strongly NP-hard even when page sizes are limited to {1, 2, 3}. In the structural part of this work, a new simpler proof for the full characterization of work functions by layers for classical caching is given and then extended to caching with variable cache size. We invent two algorithms for restricted instances of general caching building on results around caching with variable cache size.
|
guest ::
